#include <iostream>
#include <cstdlib>
#include "DoubleLinkList.h"



DoubleLinkNode::DoubleLinkNode(ElementType data, DoubleLinkNode *next, DoubleLinkNode *prev)
{
    ElementType data = NULL;
    DoubleLinkNode *next = NULL; 
    DoubleLinkNode *prev = NULL;
}


// 初始化链表
DoubleLinkList::DoubleLinkList()
{
    head = tail = new DoubleLinkNode(NULL);
    len = 0;
}

// 尾插法
void DoubleLinkList::InsertDLlistTail(ElementType element) 
{
    DoubleLinkNode *newNode = new DoubleLinkNode(element);
    if (newNode == NULL) return;
    tail->next = newNode;
    newNode->prev = tail;
    tail = newNode;
    len++;
}

// 头插法
void DoubleLinkList::InsertDLlistHead(ElementType element) 
{
    if (len == 0) 
    {
        InsertDLlistTail(element);
    } 
    else 
    {
        DoubleLinkNode *newNode = new DoubleLinkNode(element);
        newNode->next = head->next;
        head->next->prev = newNode;
        head->next = newNode;
        newNode->prev = head;
        len++;
    }
}

void DoubleLinkList::RemoveByIndex(int index, void (*freePtr)(ElementType))
{
    if(index < 0 || index >= len)
    {
        printf("删除位置非法:%d len : %d\n",index,len);
        return;
    }

    //要删除的位置是最后一个 尾巴
    if(index == len-1)
    {
        DoubleLinkNode *Prev =  tail->prev;
        Prev->next = NULL;
        //询问内存要删除的节点的数据域(void*)是否要清空
        if(freePtr != NULL)
        {
            freePtr(tail->data);
        }
        free(tail);
        tail = Prev;
        len--;
    }
    else
    {
        //TravelPoint停在要删除的前一个位置
        DoubleLinkNode *TravelPoint = head;
        for(int i = 0; i < index; i++)
        {
            TravelPoint = TravelPoint->next;
        }
        DoubleLinkNode *freeNode = TravelPoint->next;
        TravelPoint->next = freeNode->next;
        freeNode->next->prev = TravelPoint; // 一定要注意连续指向的节点是否存在
        if(freePtr != NULL)
        {
            freePtr(freeNode->data);
        }
        free(freeNode);
        len--;
    }   
}

void DoubleLinkList::RemoveByElement(ElementType element, bool (*OperPtr)(ElementType, ElementType), void (*freePtr)(ElementType))
{
    DoubleLinkNode *TravelPoint = head;
    int index = 0;
    while(TravelPoint->next != NULL)
    {
        //travelpoint的下一个节点需要删除
        if(OperPtr(TravelPoint->next->data,element) == true)
        {
            //留下这块内存的地址，后续释放，防止内存泄漏
            RemoveByIndex(index,freePtr);
        }
        else
        {
            index++;
            //避免要删除的两个相邻的值相等
            TravelPoint = TravelPoint->next;
        }
    }
}

ElementType *DoubleLinkList::FindByIndex(int index)
{
    if(index < 0 || index >= len)
    {
        printf("位置非法的查找:%d len : %d\n",index,len);
        return NULL;
    }
    DoubleLinkNode *TravelPoint = head->next;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return &TravelPoint->data;
}

void DoubleLinkList::FindByElement(ElementType element, bool (*OperPtr)(ElementType, ElementType))
{
    DoubleLinkNode *TravelPoint = head;
    while(TravelPoint->next != NULL)
    {
        //travelpoint的下一个节点需要删除
        if(OperPtr(TravelPoint->next->data,element) == true)
        {
            InsertDLlistTail(TravelPoint->next->data);
        }
        TravelPoint = TravelPoint->next;
    }
}

void DoubleLinkList::TravelDLlist(void (*PrintPtr)(ElementType))
{
    if(PrintPtr == NULL)
        return;
    DoubleLinkNode *TravelPoint = head->next;
    while(TravelPoint != NULL)
    {
        PrintPtr(TravelPoint->data);
        TravelPoint = TravelPoint->next;
    }
    std::cout<<std::endl;
}

//交换
void Swap(ElementType *value1,ElementType *value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}

//排序
void FastSort(DoubleLinkNode *start,DoubleLinkNode *end,bool (*funcPtr)(void*,void *))
{
    if(start == end)
    {
        return;
    }

    DoubleLinkNode *p1 = start;
    DoubleLinkNode *p2 = p1->next;

    //循环终止条件
    while(p2 != end)
    {
        //后面的指针的值比基准值小
        if(funcPtr(p2->data,start->data) == true)
        {
            //p1向后移动,把p1和p2的值交换
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        //交换完后,p2继续向后移动
        p2 = p2->next;
    }
    //最后将基准值和p1交换,p1之前的值都比p1小,p2之后的值都比p2大
    Swap(&start->data,&p1->data);
    //经过一轮排序,p1的位置一定在比它小的值末尾,p2一定在比它大的值的末尾
    FastSort(start,p1,funcPtr);
    FastSort(p1->next,p2,funcPtr);
}

void DoubleLinkList::DLlistSort(bool (*funcPtr)(ElementType, ElementType))
{
    FastSort(head->next,NULL,funcPtr);
}

// 清空双向链表
DoubleLinkList::~DoubleLinkList()
{
    while (head != NULL) 
    {
        DoubleLinkNode* next = head->next;
        if (ClearPtr != NULL && head->data != NULL) 
        {
            ClearPtr(head->data);
        }
        delete head;
        head = next;
    }
    tail = NULL;
    len = 0;
}

void DoubleLinkList::ClearDList(void (*ClearPtr)(ElementType))
{
    while (head != NULL) 
    {
        DoubleLinkNode* next = head->next;
        if (ClearPtr != NULL && head->data != NULL) 
        {
            ClearPtr(head->data);
        }
        delete head;
        head = next;
    }
    tail = NULL;
    len = 0;
}
